package 困难.树;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个整数 n ，表示你有一棵含有 2n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，
 * 树中编号在[1, 2n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足：
 * <p>
 * 左子节点的编号为 2 * val
 * 右子节点的编号为 2 * val + 1
 * 给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [ai, bi] 。
 * 对于每个查询，求出以下问题的解：
 * <p>
 * 在节点编号为 ai 和 bi 之间添加一条边。
 * 求出图中环的长度。
 * 删除节点编号为 ai 和 bi 之间新添加的边。
 * 注意：
 * <p>
 * 环 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
 * 环的长度是环中边的数目。
 * 在树中添加额外的边后，两个点之间可能会有多条边。
 * 请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cycle-length-queries-in-a-tree
 */
public class 查询树中环的长度_6268 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(cycleLengthQueries(5, new int[][]{
                {17, 21}, {23, 5}, {15, 7}, {3, 21}, {31, 9}, {5, 15}, {11, 2}, {19, 7}})));

    }

    /**
     * 转换思路
     * 题意可理解为求某个查询 queries[i][0] 与 queries[i][1] 到最近的公共节点
     * 的边数 + 1，可先查询其中较小的节点，和其所有上级节点 list，然后查询较大的节点
     * 一直向上寻找父节点，如果当前父节点在 list 中存在，说明已经找到最近的公共节点
     */
    public static int[] cycleLengthQueries(int n, int[][] queries) {
        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            List<Integer> list = getList(Math.min(queries[i][0], queries[i][1]));

            ans[i] = getLevel(Math.max(queries[i][0], queries[i][1]), list) + 1;
        }

        return ans;
    }

    private static List<Integer> getList(int num) {
        List<Integer> list = new ArrayList<>();
        list.add(num);

        while (num > 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = (num - 1) / 2;
            }
            list.add(num);
        }
        return list;
    }

    private static int getLevel(int num, List<Integer> list) {
        int level = 0;
        while (num > 1) {
            if (num % 2 == 0) {
                num /= 2;
            } else {
                num = (num - 1) / 2;
            }
            level++;

            for (int i = 0; i < list.size() && num <= list.get(i); i++) {
                if (num == list.get(i)) {
                    return level + i;
                }
            }
        }
        return level + list.size() - 1;
    }

}
